//
// list.h
// Usage: Base template class for `list like' class
// Create Date: 2009-02-17
// Creator: MaJiuyue
//
//----------------------------------------------------------
// ChangeLog:
//   2009-02-19  Add iterator feature
//
#ifndef _LIST_H_
#define _LIST_H_

#ifndef NULL
#define NULL 0
#endif

template<typename T>
class list_head
{
protected:
	T *next, *prev;

public:
	list_head()	{ list_init(); }
	void list_init() { 
		next = (T *)this; 
		prev = (T *)this; 
	}
	/**
     * list_add - add a new entry
     * @new: new entry to be added
     *
     * Insert a new entry after the specified head.
     * This is good for implementing stacks.
     */
	void list_add(T *_new) { __list_add(_new, (T *)this, this->next); }
	/**
     * list_add_tail - add a new entry
     * @new: new entry to be added
     *
     * Insert a new entry before the specified head.
     * This is useful for implementing queues.
     */
	void list_add_tail(T* _new) { __list_add(_new, this->prev, (T *)this); }
	/**
     * list_del - deletes entry from list.
     * @entry: the element to delete from the list.
     * Note: list_empty() on entry does not return true after this, the entry is
     * in an undefined state.
     */
	void list_del(T *entry)
	{
		if(entry->prev && entry->next)
			__list_del(entry->prev, entry->next);
		entry->next = NULL;
		entry->prev = NULL;
	}
	/**
     * list_replace - replace old entry by new one
     * @old : the element to be replaced
     * @new : the new element to insert
     *
     * If @old was empty, it will be overwritten.
     */
	void list_replace(T *_old, T *_new)
	{
		_new->next = _old->next;
		_new->next->prev = _new;
		_new->prev = _old->prev;
		_new->prev->next = _new;
	}
	void list_replace_init(T *_old, T *_new)
	{
		list_replace(_old, _new);
		_old->list_init();
	}

	/**
     * list_del_init - deletes entry from list and reinitialize it.
     * @entry: the element to delete from the list.
     */
	void list_del_init(T *entry)
	{
		__list_del(entry->prev, entry->next);
		entry->list_init();
	}

	/**
	 * list_move - delete from one list and add as another's head
	 * @list: the entry to move
	 * @head: the head that will precede our entry
	 */
	void list_move(T *list, T *head)
	{
		__list_del(list->prev, list->next);
		list_add(list, head);
	}

	/**
	 * list_move_tail - delete from one list and add as another's tail
	 * @list: the entry to move
	 * @head: the head that will follow our entry
	 */
	void list_move_tail(T *list, T *head)
	{
		__list_del(list->prev, list->next);
		list_add_tail(list, head);
	}
	/**
	 * list_is_last - tests whether @list is the last entry in list @head
	 * @list: the entry to test
	 * @head: the head of the list
	 */
	int list_is_last(const T *list)
	{
		return list->next == this;
	}

	/**
	 * list_empty - tests whether a list is empty
	 * @head: the list to test.
	 */
	bool list_empty()
	{
		return ((list_head *)this->next) == this;
	}

	/**
	 * list_is_singular - tests whether a list has just one entry.
	 * @head: the list to test.
	 */
	int list_is_singular()
	{
		return !list_empty() && (this->next == this->prev);
	}

	
	/**
	 * list_splice - join two lists
	 * @list: the new list to add.
	 * @head: the place to add it in the first list.
	 */
	void list_splice(const T *list)
	{
		if (!list_empty(list))
			__list_splice(list, (T*)this);
	}

	/**
	 * list_splice_init - join two lists and reinitialise the emptied list.
	 * @list: the new list to add.
	 * @head: the place to add it in the first list.
	 *
	 * The list at @list is reinitialised
	 */
	void list_splice_init(T *list)
	{
		if (!list_empty(list)) {
			__list_splice(list, (T*)this);
			list->list_init();
		}
	}

public:
	/**
	 * list_first_entry - get the first element from a list
	 *
	 * Note, that list is expected to be not empty.
	 */
	T* get_first_entry() { return this->next; }

	/**
	 * for_each	-	iterate over a list
	 * @pfn:	function to by called with each entry.
	 */
	virtual bool for_each(bool (*pfn)(T*))
	{
		for (T *pos = this->next; pos != this; pos = pos->next)
			if(!pfn(pos))
				return false;
		return true;
	}

	/**
	 * for_each_prev	-	iterate over a list backwards
	 * @pfn:	function to by called with each entry.
	 */
	virtual bool for_each_prev(bool (*pfn)(T*))
	{
		for (T *pos = this->prev; pos != this; pos = pos->prev)
			if(!pfn(pos))
				return false;
		return true;
	}

public:
	class iterator
	{
	private:
		T *_self;
	public:
		iterator(T * target) { _self = target; }
		iterator operator++() { _self=_self->next; return *this; }
		iterator operator--() { _self=_self->prev; return *this; }
		iterator operator=(T *target) { _self = target; return *this; }
		bool operator==(const list_head<T>::iterator& _right) const
		{
			return this->_self==_right._self;
		}
		bool operator!=(const list_head<T>::iterator& _right) const
		{
			return this->_self!=_right._self;
		} 
		T& operator*() { return *_self; }
	};
	iterator begin()
	{
		return this->next;
	}
	iterator end()
	{
		return (T *)this;
	}

	friend iterator iterator::operator++();

protected:
	/*
     * Insert a new entry between two known consecutive entries.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
	virtual void __list_add(T *_new, T *prev, T *next)
	{
		next->prev = _new;
		_new->next = next;
		_new->prev = prev;
		prev->next = _new;
	}
	/*
     * Delete a list entry by making the prev/next entries
     * point to each other.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
	virtual void __list_del(T *prev, T *next)
	{
		next->prev = prev;
		prev->next = next;
	}

	virtual void __list_splice(const T *list, T *head)
	{
		T *first = list->next;
		T *last = list->prev;
		T *at = head->next;

		first->prev = head;
		head->next = first;

		last->next = at;
		at->prev = last;
	}
};
#endif

